package algorithm.problems.math;

/**
 * Created by gouthamvidyapradhan on 01/02/2018.
 *
 * We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

 The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

 The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

 Return true if and only if the number of global inversions is equal to the number of local inversions.

 Example 1:

 Input: A = [1,0,2]
 Output: true
 Explanation: There is 1 global inversion, and 1 local inversion.
 Example 2:

 Input: A = [1,2,0]
 Output: false
 Explanation: There are 2 global inversions, and 1 local inversion.
 Note:

 A will be a permutation of [0, 1, ..., A.length - 1].
 A will have length in range [1, 5000].
 The time limit for this problem has been reduced.

 Solution: O(N) For every i, Maintain a max value up until (i - 1). If the current element at i < max value return false
 */
public class GlobalAndLocalInversions {
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{

    }

    public boolean isIdealPermutation(int[] A) {
        if(A.length == 0 || A.length == 1) return true;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i < A.length; i ++) {
            if(A[i] < max){
                return false;
            } else{
                max = Math.max(max, A[i - 1]);
            }
        }
        return true;
    }
}
